
#include <assert.h>

#include <algorithm>
#include <array>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>

class Solution {
 public:
  std::deque<int> deque_;

  void push(int val) {
    while (!deque_.empty() && val > deque_.back()) {
      deque_.pop_back();
    }
    deque_.push_back(val);
  }

  void pop(int val) {
    if (!deque_.empty() && val == deque_.front()) {
      deque_.pop_front();
    }
  }

  int front() const { return deque_.front(); }

  std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    for (int i = 0; i != k; i++) {
      push(nums[i]);
    }

    std::vector<int> ret;
    ret.push_back(front());

    for (int i = k; i != nums.size(); ++i) {
      pop(nums[i - k]);
      push(nums[i]);
      ret.push_back(front());
    }

    return ret;
  }
};

// [1,3,-1,-3,5,3,6,7]
// 3
int main(int argc, char* argv[]) {
  Solution s;
  std::vector<int> v{1, 3, -1, -3, 5, 3, 6, 7};
  std::vector<int> ret = s.maxSlidingWindow(v, 3);
  for (auto i : ret) {
    std::cout << i << " ";
  }
  return 0;
}
